1. Field of the Invention
This invention relates to the field of memory management in goal processing.
2. Background Art
Where the completion of a project is the goal that is to be achieved, a plan can be used to identify the steps that must be completed to achieve the ultimate goal (i.e., project completion). For example, in a building construction project, the goal to be achieved is the completion of the building to be constructed. A plan that includes only this step does not provide enough detail, and would likely result in a failed attempt to construct the building. Typically, a project plan for the building's construction would include some number of subgoals that would adequately define the process of constructing the building. Thus, any goal or its subgoals could have multiple layers of subgoals that further refine the plan.
To provide the flexibility necessary to accommodate unforeseen occurrences, the plan could include alternatives. Thus, if circumstances cause a step (i.e., a subgoal) chosen to achieve a step or goal to become inadequate, the goal could be achieved by using one of any number of different alternatives. If circumstances suggest the need for an alternative, an alternative is chosen based on the construction goals that have been completed (i.e., the state of the construction without the inadequate or failed subgoal), and the construction goals that remain. In some cases, it might be necessary to disregard any construction modifications associated with the failed subgoal. If the failed subgoal's construction modifications are easily identifiable, the resources needed to eliminate the modifications are reduced.
The construction project planning example illustrates the concepts associated with a goal processing system implemented in a computer system. A goal processing system has a desired problem state (i.e., finished building) that represents the goal to be achieved. The process used to achieve the desired problem state may be broken down into subgoals that can be further broken down into additional or alternative subgoals. Alternative goals identify the alternatives that may be used to achieve the initial, root goal.
The satisfaction of goals and subgoals transform a problem state from one state to the next until the desired problem state is achieved. As goals or subgoals fail during the problem-solving process, the current problem state must be returned to a state prior to the failure. Alternative subgoals may be selected and the process continues until the desired problem state is achieved.
The search for a solution using goal processing requires a large amount of the computer's resources (e.g., memory and processing time). Memory is consumed to keep track of the goals, subgoals, alternative subgoals and problem states previously processed. If a failure occurs, the problem state should be returned to the state that existed before the occurrence of the failure. Reversion to an earlier state causes the information used by the failed state to become useless. The memory used to store this information should be reclaimed for future use. The memory reclamation can consume a considerable amount of processing time unless the unused memory can be easily identified. If the memory that is no longer needed is known, all of the freed memory can be immediately reclaimed by free memory.
Systems that currently implement goal processing or problem search solutions use a goal stack to track each goal processed. As a goal is processed, the goal is pushed onto the goal stack. When a failure occurs, the system looks for an alternative for the failed goal. If there is no alternative for the failed goal, the system backtracks through each entry on the goal stack in search of an alternative. As the system backtracks, it must "pop" the goals from the goal stack, undo each goal's modifications to the problem state, and free unused memory. When an alternative goal is found for one of the goals on the goal stack, the alternative replaces this goal (i.e., the alternative is processed and placed on the goal stack).
Since configuration modifications might occur on any goal and any goal might have unexplored alternatives, each goal must be examined and its memory reclaimed individually. Additional resources are expended during this process to examine each goal on the stack and reclaim the goal stack memory that was used to store the goals examined and popped from the goal stack.
Other goal processing systems rely on garbage collection to reclaim unwanted or unused areas of memory. The garbage collection process has the same result as when memory management of each individual goal is employed. If the garbage collection is not performed after each goal is popped from the stack, processing time is expended to confirm that a portion of memory is not addressed by another memory location.
Further, if the process of collecting unused memory is left to the garbage collection function of the computer system's operating system, there is a risk that some of the unused memory will not be reclaimed. Garbage collection routines must search for any references to memory that is being considered for collection. If a reference is inadvertently retained or a referencing cell actually contains erroneous data, the garbage collection routine will assume that the referenced cell cannot be collected, and the referenced cell will not be reclaimed.
An example of a computer-based system that uses goal processing is a computer-based system for configuring systems (i.e., automobile, telephone, and desktop computer systems). Configuration systems use a model containing the components that may be used to configure a system. When a component (e.g., floppy disk drive) is requested, a goal is created to satisfy this request.
The component request goal may be comprised of subgoals that must be satisfied to satisfy the initial, or root, component request goal. For instance, a request to include a floppy disk drive in a configured system carries with it a need to determine whether a floppy disk drive controller is available to control the operations of the floppy drive. A connection must be available to connect the controller and the floppy drive. The controller and connection requirements are processed as subgoals of the floppy disk drive initial goal.
The controller and connection subgoals may be satisfied by alternative subgoals. For example, there may be several different controllers in the model that could be selected to satisfy the controller subgoal.
When the request for a floppy disk drive is encountered during goal processing, a goal entry is added to a push-down goal stack. Goal processing continues by identifying the subgoals that must be satisfied to satisfy the initial goal. Goal stack entries are created for the floppy disk drive subgoal and the connection between the drive and the controller.
As each goal is being processed or satisfied, modifications are made to the configuration. For example, as the floppy disk drive controller subgoal is being processed, an occurrence of the floppy controller is added to the configuration. At that point, the configuration includes the floppy disk drive component and occurrence and the floppy disk drive controller.
When the connection subgoal processing fails (e.g., a connection cannot be made between the floppy disk drive and controller selections), prior art goal processing systems examine each goal stack entry to find an alternative. As each goal stack entry is being examined, the goal stack entry must be popped off the stack, associated configuration modifications must be removed from the configuration, and the unused memory must be allocated to free memory. This process is repeated until an alternative is found for one of the goal stack entries, or it is determined that no alternatives exists and the initial goal cannot be satisfied.
The examination process can expend an excessive amount of processing resources as the number of non-alternative subgoals increases, since each goal stack entry is examined in search of an alternative regardless of whether they are alternative subgoals. In addition, the process of freeing memory and undoing modifications is repeated multiple times thereby creating an inefficient use of processing resources.
To reduce the resources expended when a goal failure occurs, alternative goals should be immediately and directly accessible. Goals located above the alternative goal on the goal stack should be popped off the stack simultaneously, and the associated memory immediately reclaimable as free memory for future use. Problem state modifications associated with the goals removed should be immediately identifiable such that all of the modifications can be undone in one operation, and the problem state returned to the point at which an alternative is identified.